// 版权所有2010 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 此文件实现二进制搜索。

package sort

// Search使用二进制搜索来查找并返回[0，n]中f（i）为真的最小索引i 
// ，假设在[0，n]范围内，
// f（i）==true意味着f（i+1）==true。也就是说，Search要求
// f对于输入范围[0，n）
// 的某些前缀（可能为空）为false，然后对于（可能为空）剩余部分；搜索返回
// 第一个真索引。如果没有这样的索引，搜索将返回n.
// （请注意，“未找到”返回值不是-1，例如
// strings.index）
// 只为范围内的i搜索f（i）[0，n）.
// 
// 搜索的一个常见用法是在
// 一个排序的、可索引的数据结构（如数组或切片）中查找值x的索引i。
// 在这种情况下，参数f（通常是闭包）捕获要搜索的值
// 以及数据结构的索引和排序方式。
// 
// 
// 例如，给定一个按升序排序的切片数据，
// 调用搜索（len（data），func（i int）bool{return data[i]>=23}）
// 返回最小的索引i，使得data[i]>=23。如果调用者
// 想要确定23是否在片中，则必须分别测试数据[i]==23 
// 。
// 
// 搜索按降序排序的数据将使用<=
// 运算符，而不是>=运算符。
// 
// 为了完成上面的示例，以下代码尝试在按升序排序的整数切片数据中查找值
// x:
// 
// x:=23 
// i:=sort。搜索（len（data），func（int）bool{return data[i]>=x}）
// 如果我<len（data）和data[i]==x{
// /x出现在data[i]
// }否则{
// /x不出现在data中，
// /但我是它将被插入的索引。
// 
// func GuessingGame（）{
// var s string 
// fmt.Printf（“从0到100中选择一个整数。\n”）
// 答案：=sort.Search（100，func（int）bool{
// fmt.Printf，i） 
// fmt。Scanf（“%s”、&s）
// 返回s！=“&&s[0]='y'
// }）
// fmt。Printf（“你的号码是%d.\n”，回答）
// }
// 
func Search(n int, f func(int) bool) int {
	// /定义f（-1）==false和f（n）==true。
	// 不变量：f（i-1）=假，f（j）=真。
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // 计算h时避免溢出
		// i≤ h<j 
		if !f(h) {
			i = h + 1 // 保留f（i-1）=false 
		} else {
			j = h // 保留f（j）=true 
		}
	}
	// i==j，f（i-1）==false，f（j）（=f（i））==true=>答案是i。
	return i
}

// 常见情况下的方便包装。

// SearchInts在已排序的ints片段中搜索x，并返回Search指定的索引
// 。如果x是
// 不存在（可能是len（a）），则返回值是插入x的索引。
// 切片必须按升序排序。
// 
func SearchInts(a []int, x int) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

// SearchFloat64s在float64s的排序片中搜索x，并返回Search指定的索引
// 。如果x不是
// present（可能是len（a）），则返回值是插入x的索引。
// 切片必须按升序排序。
// 
func SearchFloat64s(a []float64, x float64) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

// SearchStrings在已排序的字符串片段中搜索x，并返回Search指定的索引
// 。如果x不是
// present（可能是len（a）），则返回值是插入x的索引。
// 切片必须按升序排序。
// 
func SearchStrings(a []string, x string) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

// Search返回将SearchInts应用于接收方的结果，x.
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

// Search返回将SearchFloat64s应用于接收方的结果，x.
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }

// Search返回将searchstring应用于接收方的结果，x.
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }
